Hopefield网络

简介

Hopefield网络是一个非同步的神经网络，是一个异步的，跟BP网络不同。同时它分为两种类型，离散型和连续型。

同步与异步网络

正确设计一个递归神经网络的问题在于所有计算元素之间的充分的同步。在MP模型的网络中，我们假设每个计算元素被激活都需要消耗一定的时间。这里将要讨论的是没有全局同步的神经网络。计算节点会在不同的时间被激活，并且会在一定的时间后提供计算，这个网络是随机自动的。

双向联想记忆

在循环神经网络中(recurrent neural network)，第一层的输出的除了传到第二层之外，还会从第二层再传回自己，从而作为自己的输入。在这个联想记忆的模型中，我们可能会问这个网络在经过了多次迭代之后，是否会达到一个稳定的状态。这样的一个网络叫做谐振网络(resonance network)或者是双向联想记忆(bidirectional associative memory, BAM)。单元的激活函数是符号函数，并且信息被编码成二值。下图的这个网络将一个n维的行向量$x_0$映射到一个k维的行向量$y_0$。我们定义一个$n \times k$的权值矩阵$W$，从而让计算的第一步可以写成

$y_0=sgn(x_0 W)$

在反馈步骤中$y_0$被当作了输入，那么新的计算就变成了

$x_1^T=sgn(Wy_0^T)$

Energy Function 能量函数

动力学行为

前馈网络具备了很强的非线性映射能力，从计算的观点看，前馈型神经元网络大部分是学习网络而不具有动力学行为。反馈式网络是通过网络神经元状态的变迁而最终稳定于某一状态，从而得到联想存储或者神经计算的结果。

在反馈式网络中，所有节点（单元）都是一样的，它们之间可以相互连接，所以反馈式神经元网络可以用一个无向的完备图来表示。

网络接受一个输入，然后网络将不断演化，最终趋于一个定态，称为状态空间中的不动点吸引子，这个定态便是网络的输出图形（矢量）。

前馈网络和反馈式网络的比较

前馈型神经网络取连续或离散变量，一般不考虑输出与输入在时间上的滞后效应，只表达输出与输入的映射关系。反馈式网络也可使用离散变量也可使用连续取值，考虑输入与输出之间在时间上的延迟。因此需要用动态方程（差分方程或微分方程）来描述神经元和系统的数学模型。

Hopefield计算过程快、收敛速度快，与电子电路存在明显的对应关系，使得该网络易于理解和易于用硬件实现。

一些结论

离散型Hopfield神经元网络在不同工作方式下的性能有以下一些结论（均假设$\theta=0$，这并不失一般性）：

• 若权矩阵为对称阵，而且对角线元素非负，那么网络在异步方式下必收敛于一个稳定状态。
• 若权矩阵为对称阵，网络在同步工作方式下必收敛到一个稳定状态或者周期为2的极限环。
• 若权矩阵为正交投影矩阵，那么在同步工作方式下必收敛到一个稳定状态。
• 在稳定性分析中，同步方式工作的神经元网络可以等价于另一个异步方式工作的神经网络。

联想的原理

自联想记忆

设在学习过程中存入M个样本${X(l),l=1,2,...,M}$，使用时要求：若输入$X^l=X^a+V$，其中$X^a$是M个学习样本之一，V是偏差项（可以代表噪声、图形的缺损、畸变），要求输出为$y=X^a$，即使它复原。

异联想记忆

规定两组样本之间有一定的对应关系$X^i->y^i,l=1,2,...,M$，使用时若输入$X^l=X^a+V$（含义同上），要求输出$y=y^a$。

人脑的联想方式

人脑中对给出一种事物得出其对应的事物的途径有两种形成方式。一种是按时间顺序对相关事情进行思考，例如通过时间安排表来回忆某一阶段的工作，另一种就是通过事物本质特征的对比来确认事物的属性，从提示信息或者局部信息对事物进行回忆或确认。这两种基本方式抽象成计算技术中按地址寻找和按内容寻找两种探索方法。

网络运行过程

• 学习 形成W，与输入的样本有关系
• 初始 $v(0)=x$
• 运行 $v(t+1)=sgn(v(t)W)$
• 稳定输出 $v=x^k$

学习规则

有很多的学习方法，最常见的是Hebb学习规则：设有n个神经元互相连接，每个神经元的激活状态$x_i$只能取0或1，分别表示抑制和兴奋，学习过程中$w_{ij}$调节原则是，若i与j两个神经元同时处于兴奋状态，那么它们之间的连接应加强，即

$\Delta w_{ij}=\alpha x_i x_j,\alpha > 0$

具体实现是外积规则，对于多个模式的学习，对给定的一组向量$M={U_1,U_2,...,U_m}$，外积规则可写为

$W=\sum_{k=1}^{m}(U_k U_k^T-I),I是n \times n单位阵$

需要注意的是这事不带自环的Hopfield网络的情况，就是$w_{ij}=0$。若网络连接强度$w_{ij} \neq 0$，则称为有自环的网络。由于不带自环的Hopfield网络稳定性易于保证。

对于特定的网络规模，存在模式数目的上限，当学习的模式数大于这个上限的时候，网络不但无力记忆以后输入的模式，而且对以前的记忆也渐渐遗忘了。

## 旅行商问题 ##
### 问题介绍 ###
旅行商问题是一个最优路径问题（简称为TSP问题），是人工智能中的一个典型问题。假定有m个城市的集合${C_1,C_2,...,C_n}$，它们之间的相互距离分别是$d_{ij}(d_{ij}=d_{ji})$。试找出一条经过每个城市仅一次的最短而且回到开始的出发地的路径。传统的穷举法会导致传统的串行计算机难以在有限时间内得到圆满解决的方案。

用Hopfield网来解决TSP问题避免了计算复杂性太大的问题，因为它解决这种问题时体现了人脑的一些特征。使用一个$n \times n$神经元，用神经元的状态来表示某一个城市在某一条有效路径中的位置，例如神经元$x_i$的状态用$v_{x_i}$表示，用$C_i$表示在路径中的第i个城市。如果$v_{x_i}=1$则说明$C_x$在路径中第i个位置出现，如果这个值为0则说明在路径中的第i个位置不出现，也就是说明此时第i个位置上是其他城市

可见v矩阵可以表示n个城市的TSP问题，它的大小是$n \times n$。为了保证每个城市只去一次（当然不包括初识出发城市），那么关联矩阵v上每一行只能有一个为1，其他为0。列上的限制也是一样的。



为了解决TSP问题，必须构成这样的网络：在网络运行时，计算能量降低。网络稳定后其输出状态代表城市被访问的次序，即构成上图所示的换位阵。网络能量的极小点对应于最佳或者较佳路径的形成。

为了保证输出换位阵，因此有行约束条件


$E_1=\frac{A}{2}\sum_x\sum_i\sum_{j \neq i}v_{x_i}v_{x_j}$

其中A>0为常数。$E_1$保证当矩阵v的每一行不多于一个1时，$E_1$达到最小$E_1min=0$。

同理构成列约束条件

$E_2=\frac{B}{2}\sum_i\sum_x\sum_{y \neq x}v_{x_i}v_{y_i}$

其中B>0为常数，也保证了当矩阵v的每一列不多于一个1时，$E_2$达到最小$E_2min=0$。

构成全局约束

$E_3=\frac{C}{2}(\sum_x\sum_iv_{xi}-n)^2$

其中C>0为常数。$E_3$保证当矩阵v中的1的个数恰好为n时即整个矩阵有n个1时，$E_3$达到最小$E_3min=0$

$E_1,E_2和E_3$只和达到最小时，能保证网络输出状态矩阵v构成换位阵。